# -*- coding: utf8 -*-
r"""
Hopf algebra : Free Quasi-Symmetric functions.

This module implements method related to the Hopf algebra of permutations
called Free Quasi-Symmetric functions Hopf algebra or the 
Malvenuto-Reutenauer
Hopf algebra
(see [MalReut]_, [NCSF-VI]_, [NCSF-VII]_ and [AguSot]_).

Author:

- Jean-Baptiste Priez

References
----------

.. [MalReut] Duality between quasi-symmetrical functions and the solomon descent algebra,
    Claudia Malvenuto and
    Christophe Reutenauer

.. [NCSF-VI] Noncommutative Symmetric Function VI: Free Quasi-Symmetric Functions and Related Algebras,
    Gérard Duchamp,
    Florent Hivert and
    Jean-Yves Thibon
    
.. [NCSF-VII] Noncommutative symmetric functions VII : free quasi-symmetric functions revisited,
    Gérard Duchamp, 
    Florent Hivert,
    Jean-Christophe Novelli and 
    Jean-Yves Thibon 
    
.. [AguSot] Structure of the Malvenuto-Reutenauer Hopf algebra of permutations,
    Marcelo Aguiar and
    Frank Sottile
    
Methods
-------
"""
#*****************************************************************************
#       Copyright (C) 2012 Jean-Baptiste Priez <jbp@kerios.fr>,
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from good_hopf_algebra import GoodHopfAlgebras
from pattern import FundamentalBasis, FundamentalDualBasis, \
    getitem_for_wordlike_indices
from sage.categories.graded_hopf_algebras_with_basis import \
    GradedHopfAlgebrasWithBasis
from sage.categories.realizations import Category_realization_of_parent
from sage.combinat.free_module import CombinatorialFreeModule
from sage.misc.bindable_class import BindableClass
from sage.structure.parent import Parent
from sage.structure.unique_representation import UniqueRepresentation

#def perm_latex_term( self, m ):
#    from sage.combinat.free_module import CombinatorialFreeModule
#    if len( m ) == 0 :
#        return '1'
#    else: return self.print_options()['latex_prefix'] + ( 
#            "_{"
#            + str( m ).replace( ", ", "" ).replace( "[", "" ).replace( "]", "" )
#            + "}" )#return CombinatorialFreeModule._latex_term( self, m )


class FreeQuasisymmetricFunctions( UniqueRepresentation, Parent ):
    ''' 
    To instancie FQSym :

        EXAMPLES::

            sage: FQS = FQSym(QQ)

    To instancie some realizations :

        EXAMPLES::

            sage: F = FQS.F()
            sage: G = FQS.G()

    Some products:

        EXAMPLES::

            sage: F[1,3,2] * F[1]
            F[1, 3, 2, 4] + F[1, 3, 4, 2] + F[1, 4, 3, 2] + F[4, 1, 3, 2]

            sage: G[2,3,1] == F[3,1,2]
            True
            sage: F[2,3,1].scalar_product(F[3,1,2])
            1
    '''
    def __init__( self, R ):
        '''
        EXAMPLES::

            sage: FQS = FreeQuasisymmetricFunctions(ZZ);FQS
            Hopf algebra of Free Quasi-Symmetric functions over the Integer Ring
        '''
        from sage.categories.all import Rings
        assert( R in Rings() )
        self._base = R
        Parent.__init__( self, category = GoodHopfAlgebras( R ).WithRealizations() )

    def phi( self, indice ):
        '''
        EXAMPLES::

            sage: FQSym(QQ).phi([1,2,4])
            [1, 2, 3]
            sage: FQSym(QQ).phi([7,8,2,4])
            [3, 4, 1, 2]
        '''
        from sage.combinat.permutation import to_standard
        return to_standard( indice )

    def indices( self ):
        '''
        EXAMPLES::

            sage: FQSym(QQ).indices()
            Standard permutations
        '''
        from sage.combinat.permutation import Permutations
        return Permutations()

    def shift( self, p1, p2 ):
        '''
        EXAMPLES::
        
            sage: FQSym(QQ).shift([1,2], [2,1])
            [4,3]
        '''
        return [i + len( p1 ) for i in p2]

    def _repr_( self ):
        r"""
        EXAMPLES::

            sage: FreeQuasisymmetricFunctions(QQ)
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field
        """
        return "Hopf algebra of Free Quasi-Symmetric Functions over the %s" % self.base_ring()

    def a_realization( self ):
        return self.F()

    def dual( self ):
        r"""
        Returns the dual of the Hopf algebra FQSym.

        EXAMPLES::

            sage: FQS = FQSym(RationalField())
            sage: FQS.dual()
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field
        """
        return self

    def __init_extra__( self ):
        '''
        `\mathbb{F}_{\sigma} = \mathbb{G}_{\sigma^{-1}}`

        `\mathcal{E}_{\sigma} = \sum_{\mu \succeq \sigma}\mathbb{F}_{\mu}`

        `\mathcal{H}_{\sigma} = \sum_{\mu \preceq \sigma}\mathbb{F}_{\mu}`
        
        TESTS::

            sage: FQS = FreeQuasisymmetricFunctions(QQ)
            sage: F = FQS.F(); G = FQS.G(); E = FQS.E(); H = FQS.H()
            sage: F(G[3,1,2]) ## E <-> G
            F[2, 3, 1]
            sage: G(F[3,1,2])
            G[2, 3, 1]
            sage: F(G[3,1,2])
            F[2, 3, 1]
            sage: F(H[3,2,1]) ## F <-> H
            F[1, 2, 3] + F[1, 3, 2] + F[2, 1, 3] + F[2, 3, 1] + F[3, 1, 2] + F[3, 2, 1]
            sage: F(H[1,2,3])
            F[1, 2, 3]
            sage: F(E[3,2,1]) ## F <-> E
            F[3,2,1]
            sage: F(E[1,2,3])
            F[1, 2, 3] + F[1, 3, 2] + F[2, 1, 3] + F[2, 3, 1] + F[3, 1, 2] + F[3, 2, 1]
            sage: E(H[3,1,2])
            E[1, 2, 3] - E[2, 1, 3]

        '''
        F = self.F(); G = self.G()
        H = self.H(); E = self.E()
        m = self.m(); n = self.n()
        morph = lambda F, T, func, tri = None, comp = None: ( 
            F._module_morphism( func, codomain = T, triangular = tri, cmp = comp )
            if comp is not None else
            F._module_morphism( func, codomain = T, triangular = tri ) )

        # F <-> G
        F_to_G = morph( F, G, G.inverse_permutation )
        F_to_G.register_as_coercion()
        G_to_F = morph( G, F, F.inverse_permutation )
        G_to_F.register_as_coercion()
        # E <-> F
        E_to_F = morph( E, F, F.sum_of_fatter, tri = "lower" )
        E_to_F.register_as_coercion()
        ( ~E_to_F ).register_as_coercion()
        # H <-> F
        H_to_F = morph( H, F, F.sum_of_finer, tri = "upper" )
        H_to_F.register_as_coercion()
        ( ~H_to_F ).register_as_coercion()
        # m <-> F
        F_to_m = morph( F, m, m.sum_of_fatter_left, tri = "lower" )
        F_to_m.register_as_coercion()
        ( ~F_to_m ).register_as_coercion()
        # n <-> F
        F_to_n = morph( F, n, n.sum_of_finer_left, tri = "upper" )
        F_to_n.register_as_coercion()
        ( ~F_to_n ).register_as_coercion()


        ### MUST BE AUTOMATIC #####

        # E <-> H
        morph( E, H, ( ~H_to_F ) * E_to_F ).register_as_coercion()
        morph( H, E, ( ~E_to_F ) * H_to_F ).register_as_coercion()
        # E <-> G
        morph( E, G, F_to_G * E_to_F ).register_as_coercion()
        morph( G, E, ( ~E_to_F ) * G_to_F ).register_as_coercion()
        # H <-> G
        morph( H, G, F_to_G * H_to_F ).register_as_coercion()
        morph( G, H, ( ~H_to_F ) * G_to_F ).register_as_coercion()

        # m <-> G
        morph( m, G, F_to_G * ( ~F_to_m ) ).register_as_coercion()
        morph( G, m, F_to_m * G_to_F ).register_as_coercion()
        # m <-> E
        morph( m, E, ( ~E_to_F ) * ( ~F_to_m ) ).register_as_coercion()
        morph( E, m, F_to_m * E_to_F ).register_as_coercion()
        # m <-> H
        morph( m, H, ( ~H_to_F ) * ( ~F_to_m ) ).register_as_coercion()
        morph( H, m, F_to_m * H_to_F ).register_as_coercion()

        # n <-> G
        morph( n, G, F_to_G * ( ~F_to_n ) ).register_as_coercion()
        morph( G, n, F_to_n * G_to_F ).register_as_coercion()
        # n <-> E
        morph( n, E, ( ~E_to_F ) * ( ~F_to_n ) ).register_as_coercion()
        morph( E, n, F_to_n * E_to_F ).register_as_coercion()
        # n <-> H
        morph( n, H, ( ~H_to_F ) * ( ~F_to_n ) ).register_as_coercion()
        morph( H, n, F_to_n * H_to_F ).register_as_coercion()
        # n <-> m
        morph( n, m, F_to_m * ( ~F_to_n ) ).register_as_coercion()
        morph( m, n, F_to_n * ( ~F_to_m ) ).register_as_coercion()

    _shorthands = set( ['F', 'G', 'H', 'E', 'm', 'n'] )

    class Bases( Category_realization_of_parent ):

        def super_categories( self ):
            #print self, self.base()
            R = self.base().base_ring()
            return [self.base().Realizations(),
                    GoodHopfAlgebras( R ).Realizations(),
                    GradedHopfAlgebrasWithBasis( R ).Realizations()]

        class ParentMethods:

            def inverse_permutation( self, perm ):
                return self.monomial( perm.inverse() )

            def sum_of_finer( self, perm ):
                return self.sum_of_monomials( perm.permutohedron_smaller() )

            def sum_of_fatter( self, perm ):
                return self.sum_of_monomials( perm.permutohedron_greater() )

            def sum_of_fatter_left( self, perm ):
                return self.sum_of_monomials( perm.permutohedron_greater( side = 'left' ) )

            def sum_of_finer_left( self, perm ):
                return self.sum_of_monomials( perm.permutohedron_smaller( side = 'left' ) )

        class ElementMethods:

            def scalar_product( self, Nelt ):
                '''
                `\langle \mathbb{F}_{\sigma}, \mathbb{G}_{\mu}\rangle = \delta_{\sigma, \mu}`
                EXAMPLES::

                    sage: F = FQSym(QQ).F()
                    sage: F[3,1,2].scalar_product(F[2,3,1])
                    1
                    sage: F[3,1,2].scalar_product(F[3,1,2])
                    0
                    sage: matr = lambda X,Y, n: matrix([[X(sigma).scalar_product(Y(mu))\
                        for mu in Permutations(n)]\
                        for sigma in Permutations(n)])
                    sage: matr(F,F,3)
                    [1 0 0 0 0 0]
                    [0 1 0 0 0 0]
                    [0 0 1 0 0 0]
                    [0 0 0 0 1 0]
                    [0 0 0 1 0 0]
                    [0 0 0 0 0 1]
                    sage: G = FQSym(QQ).G()
                    sage: matr(F,G,3)
                    [1 0 0 0 0 0]
                    [0 1 0 0 0 0]
                    [0 0 1 0 0 0]
                    [0 0 0 1 0 0]
                    [0 0 0 0 1 0]
                    [0 0 0 0 0 1]
                    sage: E = FQSym(QQ).E()
                    sage: matr(F,E,3)
                    [1 0 0 0 0 0]
                    [1 1 0 0 0 0]
                    [1 0 1 0 0 0]
                    [1 1 0 0 1 0]
                    [1 0 1 1 0 0]
                    [1 1 1 1 1 1]
                    sage: H = FQSym(QQ).H()
                    sage: matr(E,H,3)
                    [1 2 2 3 3 6]
                    [0 1 0 1 1 3]
                    [0 0 1 1 1 3]
                    [0 0 0 0 1 2]
                    [0 0 0 1 0 2]
                    [0 0 0 0 0 1]
                    sage: m = FQSym(QQ).m()
                    sage: matr(m,H,3)
                    [1 0 0 0 0 0]
                    [0 1 0 0 0 0]
                    [0 0 1 0 0 0]
                    [0 0 0 0 1 0]
                    [0 0 0 1 0 0]
                    [0 0 0 0 0 1]
                    sage: matr(m,E,3)
                    [ 0  0  0  1  1  1]
                    [ 0  0  0  0 -1  0]
                    [ 0  0  0 -1  0  0]
                    [ 0  0 -1 -1  0 -1]
                    [ 0 -1  0  0 -1 -1]
                    [ 1  1  1  1  1  1]
                    sage: n = FQSym(QQ).n()
                    sage: matr(n,E,3)
                    [1 0 0 0 0 0]
                    [0 1 0 0 0 0]
                    [0 0 1 0 0 0]
                    [0 0 0 0 1 0]
                    [0 0 0 1 0 0]
                    [0 0 0 0 0 1]
                    sage: matr(n,H,3)
                    [ 1  1  1  1  1  1]
                    [-1  0 -1 -1  0  0]
                    [-1 -1  0  0 -1  0]
                    [ 0 -1  0  0  0  0]
                    [ 0  0 -1  0  0  0]
                    [ 1  1  1  0  0  0]
                    sage: matr(n,G,3)
                    [ 1  0  0  0  0  0]
                    [-1  1  0  0  0  0]
                    [-1  0  1  0  0  0]
                    [ 0 -1  0  1  0  0]
                    [ 0  0 -1  0  1  0]
                    [ 1  0  0 -1 -1  1]
                '''
                F = self.parent().realization_of().a_realization()
                return F( self ).scalar_product( Nelt )

    class Fundamental( BindableClass, FundamentalBasis ):
        '''
        This is the fundamental basis of ``FQSym``:
        
        .. MATH::
        
            \mathbb{F}_{\sigma} = 
            \sum_{w\in \mathfrak{A}^*; std(w) = \sigma} w
            
        where `\mathfrak A` is an infinite and totally ordered alphabet such that
        `\mathfrak A^*` is free monoid. (``FQSym`` defined as a sub-algebra of 
        the free algebra `\mathbb{K} \\langle \mathfrak{A} \\rangle`.)   
        
        The product of `(\mathbb{F}_\sigma)_{\sigma\in\mathfrak{G}}` is described by
        
        .. MATH::
         
            \mathbb{F}_{\sigma} \\times \mathbb{F}_{\mu} = 
            \sum_{\gamma \in \sigma \Cup \mu} \mathbb{F}_{\gamma}
        
        where `\sigma \Cup \mu` is the shifted shuffle of `\sigma` and `\mu` with. 
        We denote by `std` the standardization map which  associate to a word `w` 
        a permutation `\sigma` (see ``Permutations``).
        
        EXAMPLES::
        
            sage: F[1,2] * F[2,1]
            F[1, 2, 4, 3] + F[1, 4, 2, 3] + F[1, 4, 3, 2] + F[4, 1, 2, 3] + F[4, 1, 3, 2] + F[4, 3, 1, 2]
        
        And the coproduct is described by
        
        .. MATH::
        
            \Delta(\mathbb{F}_{\sigma}) = 
            \sum_{i\in [n]} \mathbb{F}_{\sigma_{\mid i[}} \otimes \mathbb{F}_{\sigma_{\mid [i}}
        
        where `[n] := [1,..,n]`, `i[` is the sub-interval of `[n]` defined by `[1,..,i-1]` 
        and `[i` the sub-interval defined by `[i,..,n]`.
        
        EXAMPLES::
        
            sage: F[3,1,2,4].coproduct()
            F[] # F[3, 1, 2, 4] + F[1] # F[1, 2, 3] + F[2, 1] # F[1, 2] + F[3, 1, 2] # F[1] + F[3, 1, 2, 4] # F[]
            
        (See [MalReut]_ and [NCSF-VI]_.)
        
         TESTS::
            
            sage: F = FQSym(QQ).F(); F
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the Fundamental basis
            sage: TestSuite(F).run()
        '''
        def __init__( self, FQSym ):
            FundamentalBasis.__init__( self, FQSym )
            self.print_options( prefix = "F",
                    latex_prefix = "\\mathbb{F}",
                    bracket = False )

        def dual_basis( self ):
            return self.realization_of().G()

        class Element( CombinatorialFreeModule.Element ):

            def scalar_product( self, Nelt ):
                g = self.parent()( Nelt )
                return sum( g.coefficient( al.inverse() ) * self.coefficient( al ) for al in self.support() )

    F = Fundamental

    class FundamentalDual( BindableClass, FundamentalDualBasis ):
        '''        
        The `(\mathbb{G}_{\sigma})_{\sigma\in \mathfrak{G}}`-basis is the dual basis
        of `(\mathbb{F}_{\sigma})_{\mathfrak{G}}`-basis.
        
        So FQSym is auto dual then we define this basis as following:
        
        .. MATH::
            
            \mathbb{G}_\sigma := \mathbb{F}_{\sigma^{-1}}
            
        where `\sigma^{-1}` is the inverse of `\sigma`.
        
        In this basis, the product is the convolution product:
        
        .. MATH::
        
            \mathbb{G}_\sigma \star \mathbb{G}_\mu := 
            \sum_{\gamma := u\cdot v \in \mathfrak G; 
                std(u) = \sigma;
                std(v) = \mu} \mathbb{G}_\gamma\;.
                
        EXAMPLES::
        
            sage: G[1,2] * G[2,1]
            G[1, 2, 4, 3] + G[1, 3, 4, 2] + G[1, 4, 3, 2] + G[2, 3, 4, 1] + G[2, 4, 3, 1] + G[3, 4, 2, 1]
        
        And the coproduct describes one 'un-shuffling' function:
        
        .. MATH::
        
            \Delta (\mathbb{G}_\sigma) = 
            1 \otimes \mathbb{G}_\sigma + \sum_{i\in [n]} 
                \mathbb{G}_{\sigma_{\mid i[}} \otimes
                \mathbb{G}_{std(\sigma_{\mid [i})}\;.  
                
        EXAMPLES::
        
            sage: G[3,1,2,4].coproduct()
            G[] # G[3, 1, 2, 4] + G[1] # G[2, 1, 3] + G[1, 2] # G[1, 2] + G[3, 1, 2] # G[1] + G[3, 1, 2, 4] # G[]
            
        (See [MalReut]_ and [NCSF-VI]_.)
             
         TESTS::
        
            sage: G = FQSym(QQ).G(); G
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the FundamentalDual basis
            sage: TestSuite(G).run()
        '''
        def __init__( self, FQSym ):
            '''

            EXAMPLES::

                sage: F[3,1,2] * F[1,2] # shifted shuffle of [3,1,2] and [1,2]
                F[3, 1, 2, 4, 5] + F[3, 1, 4, 2, 5] + F[3, 1, 4, 5, 2] + F[3, 4, 1, 2, 5] + F[3, 4, 1, 5, 2] + F[3, 4, 5, 1, 2] + F[4, 3, 1, 2, 5] + F[4, 3, 1, 5, 2] + F[4, 3, 5, 1, 2] + F[4, 5, 3, 1, 2]
                sage: F[3,1,2,4].coproduct() # deconcatenation of [3,1,2,4]
                F[] # F[3, 1, 2, 4] + F[1] # F[1, 2, 3] + F[2, 1] # F[1, 2] + F[3, 1, 2] # F[1] + F[3, 1, 2, 4] # F[]
            '''
            FundamentalDualBasis.__init__( self, FQSym )
            self.print_options( prefix = "G",
                    latex_prefix = "\\mathbb{G}",
                    bracket = False )

        def dual_basis( self ):
            return self.realization_of().F()

        def product_on_basis( self, p1, p2 ):
            '''
            TESTS::

                sage: F = FQSym(QQ).F(); G = FQSym(QQ).G()
                sage: F[1,2] * F[3,1,2] == G[1,2] * G[2,3,1]
                True
            '''
            from sage.combinat.words.word import Word
            from sage.combinat.words.shuffle_product import ShuffleProduct_shifted
            return self.sum_of_monomials( self.indices()( list( c ) ).inverse()
                for c in ShuffleProduct_shifted( Word( p1.inverse() ), Word( p2.inverse() ) ) )

    G = FundamentalDual

    class Elementary( BindableClass, CombinatorialFreeModule ):
        '''
        This multiplicative basis is called the elementary basis of
        FQSym, denoted: `(\mathcal{E}_\sigma)`.
         
        An element `\mathcal E_\sigma` is defined as the sum of all 
        element in the fundamental basis generated by the permutations 
        `\mu` such that `\mu` is greater than `\sigma`
        for weak order. (greater in the right permutohedron)
        
        .. MATH::
        
            \mathcal E_\sigma = \sum_{\mu \succeq \sigma} \mathbb F_\mu
            
        EXAMPLES::
            
            sage: F(E[2,1,3])
            F[2, 1, 3] + F[2, 3, 1] + F[3, 2, 1]
        
        (See [NCSF-VII]_.)  
        
        TESTS::
        
            sage: E = FQSym(QQ).E(); E
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the Elementary basis
            sage: TestSuite(E).run()
        '''
        def __init__( self, FQSym ):
            r"""

            EXAMPLES::

                sage: F = FQSym(QQ).F(); E = FQSym(QQ).E()
                sage: F(E[2,1,3])
                F[2, 1, 3] + F[2, 3, 1] + F[3, 2, 1]
                sage: E[2,1,3] * E[1]
                E[2, 1, 3, 4]
            """
            CombinatorialFreeModule.__init__( 
                self, FQSym.base_ring(), FQSym.indices(),
                category = FQSym.Bases(),
                prefix = "E", latex_prefix = "\\mathcal{E}",
                bracket = False )
        from pattern import getitem_for_wordlike_indices
        __getitem__ = getitem_for_wordlike_indices

        def dual_basis( self ):
            return self.realization_of().n()

        def product_on_basis( self, e1, e2 ):
            '''
            TESTS::

                sage: E = FQSym(QQ).E()
                sage: E[1,2] * E[2,1]
                E[1, 2, 4, 3]
                sage: E[3,1,2] * E[3,2,1]
                E[3, 1, 2, 6, 5, 4]
            '''
            if len( e1 ) == 0: return self.monomial( e2 )
            return self.monomial( 
                self.indices()( list( e1 ) + [i + max( e1 ) for i in e2] ) )

    E = Elementary

    class Homogene( BindableClass, CombinatorialFreeModule ):
        '''
        This multiplicative basis is called the homogene basis of
        FQSym, denoted: `(\mathcal{H}_\sigma)`.
         
        An element `\mathcal H_\sigma` is defined as the sum of all 
        element in the fundamental basis generated by the permutations 
        `\mu` such that `\mu` is greater than `\sigma`
        for weak order. (greater in the right permutohedron)
        
        .. MATH::
        
            \mathcal H_\sigma = \sum_{\mu \preceq \sigma} \mathbb F_\mu
            
        EXAMPLES::
            
            sage: F(H[2,1,4,3])
            F[1, 2, 3, 4] + F[1, 2, 4, 3] + F[2, 1, 3, 4] + F[2, 1, 4, 3]
        
        (See [NCSF-VII]_.)  
        
         TESTS::
        
            sage: H = FQSym(QQ).H(); H
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the Homogene basis
            sage: TestSuite(H).run()
        '''
        def __init__( self, FQSym ):
            r"""

            EXAMPLES::

                sage: F = FQSym(QQ).F(); H = FQSym(QQ).H()
                sage: F(H[2,1,3])
                F[1, 2, 3] + F[2, 1, 3]
                sage: H[2,1,3] * H[1]
                H[4, 2, 1, 3]
            """
            CombinatorialFreeModule.__init__( 
                self, FQSym.base_ring(), FQSym.indices(),
                category = FQSym.Bases(),
                prefix = "H", latex_prefix = "\\mathcal{H}",
                bracket = False )

        from pattern import getitem_for_wordlike_indices
        __getitem__ = getitem_for_wordlike_indices

        def dual_basis( self ):
            return self.realization_of().m()

        def product_on_basis( self, e1, e2 ):
            '''
            TESTS::

                sage: H = FQSym(QQ).H()
                sage: H[2,1,3,4] * H[1,2]
                H[5, 6, 2, 1, 3, 4]
                sage: H[1,2] * H[2,1]
                H[4, 3, 1, 2]
            '''
            if len( e1 ) == 0:
                return self.monomial( e2 )
            return self.monomial( 
                self.indices()( [i + max( e1 ) for i in e2] + list( e1 ) ) )

    H = Homogene

    class Monomial( BindableClass, CombinatorialFreeModule ):
        '''
        This basis `(m_\sigma)_{\mathfrak S}` defines an analogy to the basis of 
        monomial quasi-symmetric functions (.. see ``QuasiSymmetricFunctions``) for
        ``FQSym``.
        
        .. MATH::
        
            \mathbb{F}_{\sigma} = \sum_{\mu \\succeq_l \sigma} m_{\mu}
            
        where `\\succeq_l` is the weak order in the left permutohedron
        (.. see [AguSot]_). So by a Möbius inversion:
        
        EXAMPLES::
        
            sage: F(m[4,1,2,3])
            F[4, 1, 2, 3] - F[4, 1, 3, 2] - F[4, 2, 1, 3] + F[4, 3, 2, 1]
            sage: F(m[2,3,1])
            F[2, 3, 1] - F[3, 2, 1]
        
        TESTS::
        
            sage: m = FQSym(QQ).m(); m
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the Monomial basis
            sage: TestSuite(m).run()
        '''
        def __init__( self, FQSym ):
            r"""

            EXAMPLES::

                sage: F(m[2,1,3])
                F[2, 1, 3] - F[3, 1, 2]
                sage: m[1,2] * m[2,1] 
                m[1, 2, 4, 3] + m[1, 3, 4, 2] + m[1, 4, 2, 3] + 3*m[1, 4, 3, 2] + m[2, 3, 4, 1] + 2*m[2, 4, 3, 1] + m[3, 4, 2, 1] + m[4, 1, 2, 3] + 2*m[4, 1, 3, 2] + m[4, 2, 3, 1] + m[4, 3, 1, 2]
            """
            CombinatorialFreeModule.__init__( 
                self, FQSym.base_ring(), FQSym.indices(),
                category = FQSym.Bases(),
                prefix = "m", latex_prefix = "\\mathcal{M}",
                bracket = False )

        from pattern import getitem_for_wordlike_indices
        __getitem__ = getitem_for_wordlike_indices

        def dual_basis( self ):
            return self.realization_of().H()

    m = Monomial

    class Monomial2( BindableClass, CombinatorialFreeModule ):
        '''
        This basis `(n_\sigma)_{\mathfrak S}` defines an analogy to the basis of 
        monomial quasi-symmetric functions (.. see ``QuasiSymmetricFunctions``) for
        ``FQSym``.
        
        .. MATH::
        
            \mathbb{F}_{\sigma} = \sum_{\mu \\preceq_l \sigma} m_{\mu}
            
        where `\\preceq_l` is the weak order in the left permutohedron
        (.. see [AguSot]_). So by a Möbius inversion:
        
        EXAMPLES::
        
            sage: F(n[4,1,2,3])
            -F[3, 1, 2, 4] + F[4, 1, 2, 3]
            sage: F(n[2,3,1])
            -F[1, 3, 2] + F[2, 3, 1]
        
        TESTS::
        
            sage: n = FQSym(QQ).n(); n
            Hopf algebra of Free Quasi-Symmetric Functions over the Rational Field in the Monomial2 basis
            sage: TestSuite(n).run()
        '''
        def __init__( self, FQSym ):
            r"""

            EXAMPLES::

                sage: F(n[2,1,3])
                -F[1, 2, 3] + F[2, 1, 3]
                sage: n[2,1,3] * n[1]
                n[1, 3, 2, 4] + 2*n[2, 1, 3, 4] + n[2, 1, 4, 3] + 2*n[2, 3, 1, 4] + n[2, 4, 1, 3] + n[3, 2, 1, 4] + n[4, 2, 1, 3]
            """
            CombinatorialFreeModule.__init__( 
                self, FQSym.base_ring(), FQSym.indices(),
                category = FQSym.Bases(),
                prefix = "n", latex_prefix = "\\mathcal{N}",
                bracket = False )

        from pattern import getitem_for_wordlike_indices
        __getitem__ = getitem_for_wordlike_indices

        def dual_basis( self ):
            return self.realization_of().E()

    n = Monomial2
